package com.cn.codebrush.二叉树;

import java.util.Deque;
import java.util.LinkedList;

public class No114二叉树展开为链表 {
    public static void main(String[] args) {
        TreeNode tree2 = new TreeNode(1);
        TreeNode a2 = new TreeNode(2);
        TreeNode b2 = new TreeNode(5);
        TreeNode c2 = new TreeNode(3);
        TreeNode d2 = new TreeNode(4);
        TreeNode e2 = new TreeNode(3);
        TreeNode f2 = new TreeNode(6);
        TreeNode g2 = new TreeNode(3);
        TreeNode h2 = new TreeNode(3);
        tree2.left = a2;
        tree2.right = b2;
        a2.left = c2;
        a2.right = d2;
        b2.right = f2;

        flatten(tree2);
    }


    public static void flatten(TreeNode root) {
        if(root != null){
            Deque<Integer> deque = new LinkedList<>();
            flattenHelper(deque,root);
            TreeNode temp = root;
            deque.pollLast();
            while(!deque.isEmpty()){
                temp.left = null;
                temp.right = new TreeNode(deque.pollLast());
                temp = temp.right;
            }
        }
    }

    public static void flattenHelper(Deque<Integer> deque,TreeNode root) {
        if(root != null){
            deque.push(root.val);
        }

        if(root.left != null){
            flattenHelper(deque,root.left);
        }
        if(root.right != null){
            flattenHelper(deque,root.right);
        }
    }
}
